package org.speed.jdk.suanfa;

import java.awt.image.AreaAveragingScaleFilter;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Stack;

import org.aspectj.weaver.tools.cache.AsynchronousFileCacheBacking.RemoveCommand;


public class SortDemo {
	
	public static void main(String[] args) throws IOException {
		
		/**
		ListNode head = new ListNode(0);
		
		ListNode node1 = new ListNode(1);
		ListNode node2 = new ListNode(2);
		ListNode node3 = new ListNode(3);
		ListNode node4 = new ListNode(4);
		ListNode node5 = new ListNode(5);
		
		head.next = node1;
		node1.next = node2;
		node2.next = node3;
		node3.next = node4;
		node4.next = node5;
		
		
		ListNode node = SortDemo.findKthToTail(head , 1);
		System.out.println(node.val);**/
		
		
		
		TreeNode root = new TreeNode();
		root.val=0;
		
		TreeNode level1LeftNode = new TreeNode();
		level1LeftNode.val=1;
		
		
		
		
		TreeNode level2LeftNode = new TreeNode();
		level2LeftNode.val=2;	
		
		root.left = level1LeftNode;
		root.right = level2LeftNode;
		
		ArrayList<Integer> res = zigzagLevelOrder(root);
		for (Integer integer : res) {
			System.out.println(integer);
		}
	}
	
	public static ArrayList<Integer> zigzagLevelOrder (TreeNode root) {
		
		List<TreeNode> tempList = new ArrayList<SortDemo.TreeNode>();
		tempList.add(root);
		
		ArrayList<Integer> result = new ArrayList<Integer>();
		print(tempList,result );
		
		return result;
        
    }
	
	static void print(List<TreeNode> nodes,ArrayList<Integer> result) {
		
		for (TreeNode node : nodes) {
			List<TreeNode> tempList = new ArrayList<SortDemo.TreeNode>();
			
			if(node.left != null ) {
				result.add(new Integer(node.left.val));
				tempList.add(node.left);
			}
			
			if(node.right != null ) {
				result.add(new Integer(node.right.val));
				tempList.add(node.right);
			}
			
			if(!tempList.isEmpty()) {
				print(tempList,result);
			}
		}
		
	}
	
	

	public static int moreThanHalfNum_Solution(int [] array) {
		int length = array.length;
		int halfCount = length/2;
		
		
		
		
		return 0;
	}
	
	public static class TreeNode {
		
		int val = 0;
		TreeNode left = null;
		TreeNode right = null;
	    
	}
	
	
	public static class ListNode {
	    int val;
	    ListNode next = null;

	    ListNode(int val) {
	        this.val = val;
	    }
	}
	
	
	public static ListNode findKthToTail(ListNode head,int k) {
		ListNode point = head;
		int length = 0;
		while(point != null && point.next != null ) {
			length++;
			point = point.next;
		}
		
		if(k > length ) {
			return null;
		}
		
		point = head;
		int step = 0;
		while(step !=  length - k + 1 ) {
			point = point.next;
			step++;
		}
		
		return point;
    }
	
	
	
	static int[] twoSum(int[] numbers, int target) {
		
		int[] result = new int[2];
		for (int i = 0 ; i < numbers.length; i ++ ) {
			
			if(target < numbers[i] ) {
				continue;
			}
			
			int temp = target - numbers[i];
			result[0] = i+1;//下标从0开始
			
			for (int j = i + 1; j < numbers.length; j++) {
				if(temp == numbers[j]) {
					result[1] = j+1;//下标从0开始
					return result;
				}
			}
		}
		
		return result;
	}
	
	
	
	/**
	 * 数字反转
	 * @param number
	 * @return
	 */
	static int revers(int number) {
		if(number == 0 ) {
			return number;
		}
		
		boolean flag = true;
		if(number < 0 ) {
			number = number * -1;
			flag = false;
		}
		
		String sNumber = String.valueOf(number);
		char[] arrays = sNumber.toCharArray();
		StringBuffer stringBuffer = new StringBuffer();
		
		int index = arrays.length - 1;
		while(index >= 0 ) {
			char attr = arrays[index];
			if(attr == '0' && stringBuffer.toString().length() == 0 ) {
				
			}else {
				stringBuffer = stringBuffer.append(attr);
			}
			
			index--;
		}
		
		return Integer.parseInt(stringBuffer.toString()) * (flag ? 1 : (-1));
	}
	
	/**
	 * 符合匹配
	 * @param source
	 */
	static void test(String source) {
		Stack<String> stack = new Stack<String>();
		
		char[] arrays = source.toCharArray();
		for (char attr : arrays) {
			if(!stack.isEmpty()) {
				String p = stack.pop();
				String q = String.valueOf(attr);
				if(!match(p,q)) {
					stack.push(p);
					stack.push(q);
				}
			}else {
				stack.push(String.valueOf(attr));
			}
		}
		
		boolean result = stack.isEmpty() ? true : false;
		
		System.out.println("source:" + source + ",result=" + result);
	}
	
	static boolean match(String a,String b ) {
		
		if("(".equals(a) && ")".equals(b)) {
			return true;
		}
		
		if("[".equals(a) && "]".equals(b)) {
			return true;
		}
		
		if("{".equals(a) && "}".equals(b)) {
			return true;
		}
		
		return false;
	}
	
	static int lastWordLength(String source) {
		if(source == null || source.length() == 0 ) {
			return 0;
		}
		
		if(!source.contains(" ")) {
			return source.length();
		}
		
		int index = source.length() - 1 ;
		char str = '1';
		int wordLength = 0;
		do {
			str = source.charAt(index);
			index--;
			wordLength++;
		} while (str != ' ');
		
		return wordLength - 1;
	}
	
	
	/**
	 * 字符串反转
	 * 1、栈完成
	 * 2、对折
	 * @param target
	 */
	static void reverse(String target) {
		System.out.println("target:" + target);
		
		char[] arrays = target.toCharArray();
		Stack<String> stacks = new Stack<String>();
		for (char attr : arrays) {
			stacks.push(String.valueOf(attr));
		}
		
		StringBuffer sBuffer = new StringBuffer();
		while(!stacks.isEmpty()) {
			sBuffer = sBuffer.append(stacks.pop());
		}
		
		String result = sBuffer.toString();
		System.out.println("result:" + result);
	}
	
	
	/**
	 * 冒泡算法
	 * 时间复杂度：O(n^2)
	 * 空间复杂度：O(1)
	 * @param arrays
	 */
	static void sort(int[] arrays) {
		print(arrays,true);
	
		int length = arrays.length;
		for (int i = 0 ; i < length; i++ ) {
			for(int j = i+1; j < length ; j++ ) {
				if(arrays[j-1] > arrays[j]) {
					int temp = arrays[j-1];
					arrays[j-1] = arrays[j];
					arrays[j] = temp;
				}
			}
		}
		
		print(arrays,false);	
		
	}

	
	static void print(int[] arrays,boolean noSort) {
		StringBuffer sBuffer = new StringBuffer(noSort ? "排序前:" : "排序后:");
		int length = arrays.length;
		for (int index = 0 ; index < length ; index++ ) {
			int attr = arrays[index];
			sBuffer = sBuffer.append(attr);
			if(index != length - 1 ) {
				sBuffer = sBuffer.append(",");
			}
		}
		
		sBuffer.append("\n");
		System.out.print(sBuffer.toString());
	}
}
